package com.data.algorithm.search;


/**
 * 插值查找法
 *
 * @author wangjie
 * @version V1.0
 * @date 2020/3/30
 */
public class InsertValueSearch {


    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
        int valueSearch = insertValueSearch(arr, 0, arr.length - 1, 1);
        System.out.println("valueSearch=" + valueSearch);
    }


    public static int insertValueSearch(int[] arr, int left, int right, int findVal) {
        System.out.println("插值查找次数~~");
        if (left <= right && findVal >= arr[0] && findVal <= arr[arr.length - 1]) {
            int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
            int midVal = arr[mid];
            if (findVal > midVal) {
                return insertValueSearch(arr, mid + 1, right, findVal);
            } else {
                return findVal < midVal ? insertValueSearch(arr, left, mid - 1, findVal) : mid;
            }
        } else {
            return -1;
        }
    }
}

